Решение задачи линейного программирования
ТЕМА: ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
ЗАДАЧА 2.А. Решение задачи линейного программирования графическим методом
Внимание!
Это ОЗНАКОМИТЕЛЬНАЯ ВЕРСИЯ работы №2073, цена оригинала 200 рублей. Оформлена в программе Microsoft Word.
Оплата. Контакты.
Вариант 7. Найти максимальное и минимальное значения линейной функции Ф = 2x1 — 2·x2 при ограничениях: x1 + х2 ≥ 4;
— х1 + 2·х2 ≤ 2;
x1 + 2·х2 ≤ 10;
х i ≥ 0, i = 1,2.
Решение:
Заменив условно знаки неравенств на знаки равенств, получим систему уравнений x1 + х2 = 4;
— х1 + 2·х2 = 2;
x1 + 2·х2 = 10.
Построим по этим уравнениям прямые, затем в соответствии со знаками неравенств выделим полуплоскости и получим их общую часть – область допустимых решений ОДР – четырехугольник MNPQ.
Минимальное значение функ-
ции — в точке М(2; 2)
Фmin = 2·2 — 2·2 = 0.
Максимальное значение достигается в точке N (10; 0),
Фmax = 2·10 — 2·0 = 20.
Вариант 8. Найти максимальное и минимальное значения
линейной функции Ф = x1 + x2
при ограничениях: x1 — 4·х2 — 4 ≤ 0;
3·х1 — х2 ≥ 0;
x1 + х2 — 4 ≥ 0;
х i ≥ 0, i = 1,2.
Решение:
Заменив условно знаки неравенств на знаки равенств, получим систему уравнений x1 — 4·х2 = 4 ;
3·х1 — х2 = 0;
x1 + х2 = 4 .
Построим по этим уравнениям прямые, затем в соответствии со знаками неравенств выделим полуплоскости и получим их общую часть – область допустимых решений ОДР – неограниченный многоугольник MNPQ.
Минимальное значение функ-
ции – на прямой NP, например
в точке Р(4; 0 )
Фmin = 4 + 0 = 4.
ОДР сверху не ограничена, следовательно, Фmax = + ∞.
Вариант 10. Найти максимальное и минимальное значения
линейной функции Ф = 2·x1 — 3·x2
при ограничениях: x1 + 3·x2 ≤ 18;
2·х1 + х2 ≤ 16;
х2 ≤ 5;
3·х1 ≤ 21;
х i ≥ 0, i = 1,2.
Заменив условно знаки неравенств знаками равенств, получим систему уравнений
x1 + 3·x2 = 18 (1);
2·х1 + х2 = 16 (2);
х2 = 5 (3);
3·х1 = 21 (4).
Построим по этим уравнениям прямые, затем в соответствии со знаками неравенств выделим полуплоскости и получим их общую часть — область допустимых решений ОДР – многоугольник MNPQRS.
Построим вектор Г(2; -3) и через начало координат проведем линию уровня – прямую .
Перемещаем линию уровня в направлении , значение Ф при этом растет. В точке S(7; 0) целевая функция достигает максимума Фmax=2·7–3·0= = 14. Перемещаем линию уровня в направлении , значение Ф при этом убывает. Минимальное значение функции — в точке N(0; 5)
Фmin = 2·0 – 3·5 = –15.
ЗАДАЧА 2.B. Решение задачи линейного программирования
аналитическим симплексным методом
Вариант 7. Минимизировать целевую функцию Ф = x1— x2+ x3+ x4+ x5 — x6
|
при ограничениях: x1 + x4 +6·x6 = 9,
3·x1 + x2 – 4·x3 + 2·x6 = 2,
x1 + 2·x3 + x5 + 2·x6 = 6.
Решение:
Количество неизвестных n=6, количество уравнений m=3. Следовательно, r = n-m = 3 неизвестных можно принять в качестве свободных. Выберем x1, x3 и x6.
Базисные переменные x2,x4 и x5 выразим через свободные и приведем систему к единичному базису
х2 = 2 — 3·x1 + 4·x3 – 2·x6
x4 = 9 – x1 – 6·x6 (*)
x5 = 6 – x1 — 2·x3 – 2·x6
Целевая функция будет иметь вид:
Ф = x1 — 2 + 3·x1 — 4·x3 + 2·x6 + x3 + 9 – x1 – 6·x6 +6 – x1 — 2·x3 – 2·x6 – x6 =
= 13 + 2·x1 — 5·x3 – 7·x6
Положим x1 = x3 = x6 = 0, при этом базисные переменные примут значения x2 = 2; x4 = 9; x5 = 6, то есть, первое допустимое решение (0; 2; 0; 9; 6; 0), целевая функция Ф1 = 13.
Переменные х3 и х6 входят в целевую функцию с отрицательными коэффициентами, следовательно, при увеличении их значений величина Ф будет уменьшаться. Возьмем, к примеру, х6. Из 1-го уравнения системы (*) видно, что увеличение значения x6 возможно до x6 = 1 (пока x2 ³ 0). При этом x1 и x3 сохраняют значения, равные нулю. Теперь в качестве базисных переменных примем х4, х5, х6, в качестве свободных – х1, х2, х3. Выразим новые базисные переменные через новые свободные. Получим
х6 = 1 – 3/2·x1 – 1/2·x2 + 2·x3
x4 = 3 + 8·x1 + 3·x2 – 12·x3
x5 = 4 + 2·x1 + x2 – 6·x3
Ф = 6 + 25/2 ·x1 + 7/2·x2 – 19·x3
Присвоим свободным переменным нулевые значения, то есть, x1 =x2= x3=0, при этом х6 = 1, x4 = 3, x5 = 4, то есть, третье допустимое решение (0; 0; 0; 3; 4; 1). При этом Ф3 = 6.
Переменная x3 входит в целевую функцию с отрицательным коэффициентом, следовательно увеличение x3 относительно нулевого значения приведет к снижению Ф. Из 2-го уравнения видно, что x3 может возрастать до 1/4, из 3-го уравнения – до 2/3. Второе уравнение более критично. Переменную x3 переведем в число базисных, x4 — в число свободных.
Теперь в качестве новых свободных переменных примем x1, x2 и x4. Выразим через них новые базисные переменные x3, x5, x6. Получим систему
х3 = 1/4 + 2/3·x1 + 1/4·x2 – 1/12·x4
x5 = 5/2 — 2·x1 – 1/2·x2 + 1/2·x4
x6 = 3/2 – 1/6·x1 – 1/6·x4
Целевая функция примет вид
Ф = 5/4 — 1/6·x1 — 5/4·x2 + 19/12·x4
Переменные х1 и х2 входят в целевую функцию с отрицательными коэффициентами, следовательно, при увеличении их значений величина Ф будет уменьшаться. Возьмем, например, х2. Из 2-го уравнения системы видно, что увеличение значения x2 возможно до x2 = 5 (пока x5 ³ 0). При этом x1 и x4 сохраняют нулевые значения, значения других переменных равны x3 = 3/2; x5 = 0, x6 = 3/2, то есть, четвертое допустимое решение (0; 5; 3/2; 0; 0; 3/2). При этом Ф4 = 5/4.
Теперь в качестве новых свободных переменных примем x1, x4 и x5. Выразим через них новые базисные переменные x2, x3, x6. Получим систему
х2 = 5 — 4·x1 + x4 – 2·x5
x3 = 3/2 – 1/3·x1 + 1/6·x4 — 1/2·x5
x6 = 3/2 – 1/6·x1 – 1/6·x4
Целевая функция примет вид
Ф = — 5 + 29/6·x1 + 1/3·x4 + 5/2·x5
Коэффициенты при обеих переменных в выражении для Ф положительные, следовательно, дальнейшее уменьшение величины Ф невозможно.
То есть, минимальное значение Фmin = — 5, последнее допустимое решение (0; 5; 3/2; 0; 0; 3/2) является оптимальным.
Вариант 8. Максимизировать целевую функцию Ф = 4·x5 + 2·x6
|
при ограничениях: x1 + x5 + x6 = 12;
x2 + 5·x5 — x6 = 30;
x3 + x5 — 2·x6 = 6;
2·x4 + 3·x5 — 2·x6 = 18;
Решение:
Количество уравнений равно 4, количество неизвестных – 6. Следовательно r = n – m = 6 – 4 = 2 переменных можем выбрать в качестве свободных, 4 переменных – в качестве базисных. В качестве свободных выберем x5 и x6, в качестве базисных — x1, x2, x3, x4. Выразим базисные переменные через свободные и приведем систему уравнений к единичному базису
x1 = 12 — x5 — x6;
x2 = 30 — 5·x5 + x6;
x3 = 6 — x5 + 2·x6;
x4 = 9 — 3/2·x5 + x6;
Целевую функцию запишем в виде Ф = 4·x5 + 2·x6 . Присвоим свободным переменным нулевые значения x5 = x6 = 0. При этом базисные переменные примут значения x1 = 12, x2 = 30, x3 = 6, x4 = 9, то есть, получим первое допустимое решение (12, 30, 6, 9, 0, ) и Ф1 = 0.
В целевую функцию обе свободные переменные входят с положительными коэффициентами, то есть, возможно дальнейшее увеличение Ф. Переведем, например, x6 в число базисных. Из уравнения (1) видно, что x1 = 0 при x5 = 12, в (2) ÷ (4) x6 входит с положительными коэффициентами. Перейдем к новому базису: базисные переменные – x6, x2, x3, x4, свободные — x1, x5. Выразим новые базисные переменные через новые свободные
х6 = 12 — x1 — x5;
x2 = 42 — x1 — 6·x5;
x3 = 30 — 2·x1 — 3·x5;
x4 = 21 — x1 — 5/2·x5;
Целевая функция примет вид Ф = 24 — 2·x1 + 2·x5;
Присвоим свободным переменным нулевые значения x1 = x5 = 0. При этом базисные переменные примут значения x6 =12, x2 =42, x3 = 30, x4 = 21, то есть, получим второе допустимое решение (0, 42, 30, 21, 0, 12 ) и Ф2 = 24.
В целевую функцию x5 входит с положительным коэффициентом, то есть, возможно дальнейшее увеличение Ф. Перейдем к новому базису: базисные переменные – x6, x5, x3, x4, свободные — x1, x2. Выразим новые базисные переменные через новые свободные
х6 = 5 — 5/6·x1 + 1/6·x2;
x5 = 7 — 1/6·x1 — 1/6·x2;
x3 = 9 — 3/2·x1 + 1/2·x2;
x4 = 7/2 — 7/12·x1 + 5/12·x5;
Целевая функция примет вид Ф = 38 – 7/2·x1 – 1/3·x2;
Присвоим свободным переменным нулевые значения x1 = x2 = 0. При этом базисные переменные примут значения x6 = 5, x5 = 7, x3 = 9, x4 = 7/2, то есть, получим третье допустимое решение Х3 = (0, 0, 9, 7/2, 7, 5 ) и Ф3 = 38.
В целевую функцию обе переменные входят с отрицательными коэффициентами, то есть, дальнейшее увеличение Ф невозможно.
Следовательно, последнее допустимое решение является оптимальным, то есть, Хопт = (0, 0, 9, 7/2, 7, 5) и Фmax = 38.
Вариант 10. Максимизировать целевую функцию Ф = x2 + x3
|
при ограничениях: x1 — x2 + x3 = 1,
x2 — 2·х3 + х4 = 2.
Решение:
Система уравнений — ограничений совместна, так как ранги матрицы системы уравнений и расширенной матрицы одинаковы и равны 2. Следовательно, две переменные можно принять в качестве свободных, две другие переменные — базисные — выразить линейно через две свободные.
Примем за свободные переменные x2 и х3.Тогда базисными будут переменные х1 и х2, которые выразим через свободные
x1 = 1 + x2 — x3; (*)
x4 = 2 — x2 + 2·x3;
Целевая функция уже выражена через x2 и x3, то есть, Ф = x2 + x3.
При х2=0 и х3=0 базисные переменные будут равными х1 = 1, х4 = 2.
Имеем первое допустимое решение Х1 = (1, 0, 0, 2), при этом Ф1 = 0.
Увеличение Ф возможно при увеличении, например, значения х3, который входит в выражение для Ф с положительным коэффициентом (x2 при этом остается равным нулю). В первое уравнение системы (*) видно, что х3 можно увеличивать до 1 (из условия х1 ³0), то есть это уравнение накладывает ограничение на увеличение значения х3. Первое уравнение системы (*) является разрешающим. На базе этого уравнения переходим к новому базису, поменяв х1 и х3 местами. Теперь базисными переменными будут х3 и x4, свободными — x1 и x2. Выразим теперь х3 и x4 через х1 и х2.
Получим: x3 = 1 — x1 + x2; (**)
x4 = 4 — 2·x1 + x2;
Ф = х2 + 1 — х1 + х2 = 1 — x1 + 2·x2
Приравняв нулю свободные переменные, получим второе допустимое базисное решение Х2= (0; 0; 1; 4), при котором Ф2=1.
Увеличение Ф возможно при увеличении х2. Увеличение же х2, судя по последней системе уравнений (**), не ограничено. Следовательно, Ф будет принимать все большие положительные значения, то есть, Фмах = + ¥.
Итак, целевая функция Ф не ограничена сверху, потому оптимального решения не существует.
ЗАДАЧА 2.D. Составить задачу, двойственную к приведенной
исходной задаче.
Вариант 7. Максимизировать целевую функцию Ф = 2×х1 — х4
при ограничениях: х1 + х2 = 20,
х2 + 2×х4 ≥ 5,
х1 + х2 + х3 ≤ 8,
хi ≥ 0 (i = 1, 2, 3, 4)
Решение:
Приведем систему ограничений к единому, например, каноническому виду, введя дополнительные переменные во 2-ое и 3-е уравнения
х1 + х2 = 20,
х2 + 2×х4 – х5 = 5,
— х1 + х2 + х3 + х6 = 8.
Получили несимметричную задачу 2-го типа. Двойственная задача будет иметь вид:
Минимизировать целевую функцию F = 20×у1 + 5×y2 + 8×y3
при y1 — y3 ≥ 2,
y1 + y2 + y3 ≥ 0,
y3 ≥ 0,
2×y2 ≥ 1,
-y2 ≥ 0,
y3 ≥ 0.
Вариант 8. Максимизировать целевую функцию Ф = х2 — х4 — 3×х5
при ограничениях: х1 + 2×х2 — х4 + х5 = 1,
— 4×х2 + х3 + 2×х4 — х5 = 2,
3×х2 + х5 + х6 = 5,
xi ≥ 0, (i = 1, 6)
Решение:
Имеем исходную задачу на максимизацию с системой ограничений в виде уравнений, то есть, пара двойственных задач имеет несимметричный вид 2-го типа, математическая модель которых в матричной форме имеет вид:
Исходная задача: Двойственная задача:
Ф = С×Х max F = BТ×Y min
при А×Х = В при AТ×Y ≥ СТ
Х ≥ 0
В исходной задаче матрица-строка коэффициентов при переменных в целевой функции имеет вид С = (0; 1; 0; -1; -3; 0),
матрица-столбец свободных членов и матрица коэффициентов при переменных в системе ограничений имеют вид
1 1 2 0 -1 1 0
В = 2 , А = 0 — 4 1 2 -1 0
5 0 3 0 0 1 1
Найдем транспонированную матрицу коэффициентов, матрицу-строку коэффициентов при переменных в целевой функции и матрицу-столбец свободных членов
1 0 0 0
2 4 3 1
0 1 0 0 ВТ = (1; 2; 5)
AT = -1 2 0 СТ = -1
1 -1 1 -3
0 0 1 0
Двойственная задача запишется в следующем виде:
найти минимальное значение целевой функции F = y1 + 2×y2 + 5×y3
при ограничениях y1 ≥ 0,
2×y1 — 4×y2 + 3×y3 ≥ 1,
y2 ≥ 0,
— y1 + 2×y2 ≥ -1,
y1 — y2 + y3 ≥ -3,
y3 ≥ 0,
Вариант 10. Минимизировать функцию Ф = х1 + х2 + х3
при ограничениях: 3×х1 + 9×х2 + 7×х3 ≥ 2,
6×х1 + 4·х2 + 5×х3 ≥ 3,
8×х1 + 2·х2 + 4×х3 ≥ 4,
Решение:
Имеем исходную задачу на минимизацию с системой ограничений в виде неравенств, то есть, пара двойственных задач имеет симметричный вид 3-го типа, математическая модель которых в матричной форме имеет вид:
Исходная задача Двойственная задача
Ф = С× Х min F = BТ×Y max
при А × Х ≥ В при AТ ×Y ≤ СТ
Х ≥ 0 Y ≥ 0
В исходной задаче матрица-строка коэффициентов при переменных в целевой функции, матрица-столбец свободных членов и матрица коэффициентов при переменных в системе ограничений имеют вид
2 3 9 7
С = (1; 1; 1), В = 3 , А = 6 4 5
4 8 2 4
Найдем матрицы двойственной задачи
2 3 6 8
ВT = (2; 3; 4) СT = 3 AT = 9 4 2
4 7 5 4
Двойственная задача формулируется в виде:
Максимизировать целевую функцию F = 2y1 + 3y2 + 4y3
при ограничениях 3×y1 + 6×y2 + 8×y3 ≤ 1,
9×y1 + 4×y2 + 2×y3 ≤ 1,
7×y1 + 5×y2 + 4×y3 ≤ 1,
yi ≥ 0 (i = 1, 2, 3)
ЗАДАЧА 2.С. Решение задачи линейного программирования с помощью симплексных таблиц.
Вариант 7. Максимизировать целевую функцию Ф = 2·x1 — x2 + 3·x3+ 2·x4
|
при ограничениях: 2·x1 + 3·x2 — x3 + 2·x4 ≤ 4,
x1 — 2·x2 + 5·x3 — 3·x4 ≥ 1,
4·x1 + 10·x2 +3·x3 + x4 ≤ 8.
Решение:
Приведем систему ограничений к каноническому виду
2·x1 + 3·x2 — x3 + 2·x4 + z1 = 4, (1)
x1 — 2·x2 + 5·x3 — 3·x4 — z2 = 1, (2)
4·x1 + 10·x2 +3·x3 + x4 + z3 = 8. (3)
Имеем систему 3-х уравнений с 7-ю неизвестными. Выберем в качестве базисных 3 переменных x1, z1, z3, в качестве свободных — x2, x3 , x4, z2 , выразим через них базисные переменные.
Из (2) имеем x1 = 1 + 2·x2 — 5·x3 + 3·x4 + x6
Подставим в (1) и (3), получим
x1 — 2·x2 + 5·x3 — 3·x4 — z2 = 1,
z1 + 7·x2 — 11·x3 + 8·x4 + 2·z2 = 2,
z3 + 18·x2 — 17·x3 + 13·x4 + 4·z2 = 4,
Ф — 3·x2 + 7·x3 — 8·x4 — 2· z2 = 2.
Составим симплекс-таблицу
I итерация Таблица 1
Базисн. перем. | Свобод. перем. |
x1 |
x2 |
x3 |
x4 |
z1 |
z2 |
z3 |
bi/aip |
aip/aqp |
x1 | 1 | 1 | — 2 | 5 | — 3 | 0 | — 1 | 0 | 3/8 | |
z1 | 2 | 0 | 7 | -11 | 1 | 2 | 0 | 1/ 4 | 1/8 | |
z3 | 4 | 0 | 18 | -17 | 13 | 0 | 4 | 1 | 4/13 | 13/8 |
Ф | 2 | 0 | — 3 | 7 | — 8 | 0 | — 2 | 0 | 1 |
Х1 = (1; 0; 0; 0; 2; 0; 4) Ф1 = 2.
II итерация Таблица 2
x1 | 14/8 | 1 | 5/8 | 7/8 | 0 | 3/8 | -2/8 | 0 | 2 | — 1 |
x4 | 1/ 4 | 0 | 7/8 | -11/8 | 1 | 1/8 | 2/8 | 0 | 11/7 | |
z3 | 6/8 | 0 | 53/8 | 0 | -13/8 | 6/8 | 1 | 6/7 | 8/7 | |
Ф | 4 | 0 | 4 | — 4 | 0 | 1 | 0 | 0 | 32/7 |
Х2 = (14/8; 0; 0; 1/4; 0; 0; 4) Ф2 = 4.
III итерация Таблица 3
x1 | 1 | 1 | — 6 | 0 | 0 | -1 | — 1 | 1/2 | ||
x4 | 10/ 7 | 0 | 79/7 | 0 | 1 | -17/7 | 10/7 | 11/7 | 11/7 | |
x3 | 6/7 | 0 | 53/7 | 1 | 0 | -13/7 | 6/7 | 8/7 | 13/14 | |
Ф | 52/7 | 0 | 240/7 | 0 | 0 | -45/7 | 24/7 | 32/7 | 45/14 |
Х3 = (1; 0; 6/7; 10/7; 0; 0; 0) Ф3 = 52/7.
IV итерация Таблица 4
z1 | 1/ 2 | 1/2 | — 3 | 0 | 0 | 1 | -1/2 | -1/2 | ||
x4 | 37/ 14 | 17/14 | 56/14 | 0 | 1 | 0 | 3/14 | 5/14 | ||
x3 | 25/14 | 13/14 | 28/14 | 1 | 0 | 0 | -1/14 | 3/14 | ||
Ф | 149/14 | 45/14 | 15 | 0 | 0 | 0 | 3/14 | 19/14 |
Х4 = (0; 0; 25/14; 37/14; 1/2; 0; 0) Ф4 = 149/14.
В индексной строке последней таблицы нет отрицательных чисел, то есть, в выражении для целевой функции все Гi < 0. Имеем случай I, следовательно, последнее базисное решение является оптимальным.
Ответ: Фmax= 149/14,
оптимальное решение (0; 0; 25/14; 37/14; 1/2; 0; 0)
Вариант 8. Минимизировать целевую функцию Ф = 5·x1 — x3
|
при ограничениях: x1 + x2 + 2·x3 — x4 = 3,
x2 + 2· x4 =1,
Решение:
Количество переменных равно 4, ранг матрицы — 2, следовательно количество свободных переменных равно r = 4 — 2 = 2, количество базисных тоже 2. В качестве свободных переменных примем х3, х4, базисные переменные x1, x2 выразим через свободные и приведем систему к единичному базису:
x2 = 1 — 2· x4,
x1 = 3 — x2 — 2·x3 + x4 = 3 – 1 + 2· x4— 2·x3 + x4 = 2 — 2·x3 + 3· x4
Ф = 5·x1 — x3 = 5·(2 — 2·x3 + 3· x4) — x3 = 10 — 10·x3 + 15· x4 — x3 = 10 — 11·x3 + 15· x4
Запишем систему уравнений и целевую функцию в удобном для симплекс-таблицы виде, то есть, x2 + 2· x4= 1,
x1+2·x3 — 3· x4 = 2
Ф + 11·x3 — 15· x4= 10
Составим таблицу
I итерация Таблица 1
Базисн. перем. | Свобод. перем. |
Х1 |
Х2 |
Х3 |
Х4 |
bi/aip |
aip/aqp |
X1 | 2 | 1 | 0 | — 3 | 1/2 | ||
X2 | 1 | 0 | 1 | 0 | 2 | ||
Ф | 10 | 0 | 0 | 11 | — 15 | — 11/2 |
Х1 = (2; 1; 0; 0) Ф1 = 10.
II итерация Таблица 2
X3 | 1 | 1/2 | 0 | 1 | -3/2 | 3/4 | |
X2 | 1 | 0 | 1 | 0 | 1/2 | ||
Ф | — 1 | — 11/2 | 0 | 0 | 3/2 | — 3/4 |
Х2 = (0; 1; 1; 0) Ф2 = -1.
III итерация Таблица 3
X3 | 7/4 | 1/2 | 3/4 | 1 | 0 | ||
X4 | 1/2 | 0 | 1/2 | 0 | 1 | ||
Ф | — 7/4 | — 11/2 | — 3/4 | 0 | 0 |
Х3 = (0; 0; 7/4; 1/2) Ф3 = -7/4.
В индексной строке последней таблицы нет положительных чисел, то есть, в выражении для целевой функции все Гi > 0. Имеем случай I, следовательно, последнее базисное решение является оптимальным.
Ответ: Фmin = -7/4, оптимальное решение (0; 0; 7/4; 1/2)
********************
Вариант 10. Минимизировать целевую функцию Ф = x1 + x2,
|
при ограничениях: x1 –2·x3 + x4 = 2,
x2 – x3 + 2·x4 = 1,
Решение:
Количество переменных равно 5, ранг матрицы — 3, следовательно количество свободных переменных равно r = 6-3 = 2. В качестве свободных переменных примем х3 и х4, в качестве базисных — x1, x2, x5. Все уравнения системы уже приведены к единичному базису (базисные переменные выражены через свободные), но записаны в виде, не удобном к применению симплекс-таблиц. Запишем систему уравнений в виде
x1 — 2·x3 + x4 = 2
x2 — x3 +2·x4 = 1
x5 + x3 — x4. = 5
Целевую функцию выразим через свободные переменные и запишем в виде Ф — 3·x3 +3·x4 = 3
Составим таблицу
I итерация Таблица 1
Базисн. перем. | Свобод. перем. |
х1 |
х2 |
х3 |
х4 |
х5 |
bi/aip |
aip/aqp |
х1 | 2 | 1 | 0 | -2 | 1 | 0 | 2 | -1/2 |
х2 | 1 | 0 | 1 | -1 | 0 | 1/2 | 1/2 | |
х5 | 5 | 0 | 0 | 1 | -1 | 1 | 1/2 | |
Ф | 3 | 0 | 0 | -3 | 3 | 0 | -3/2 |
Х1 = (2; 3; 0; 0; 5) Ф1 = 3.
Таблица 2
х1 | 3/2 | 1 | -1/2 | -3/2 | 0 | 0 | ||
х4 | 1/2 | 0 | 1/2 | -1/2 | 1 | 0 | ||
х5 | 11/2 | 0 | 1/2 | 1/2 | 0 | 1 | ||
Ф | 3/2 | 0 | -3/2 | -3/2 | 0 | 0 |
Х2 = (3/2; 0; 0; 1/2; 11/2) Ф2 = 3/2.
В индексной строке последней таблицы нет положительных чисел, то есть, в выражении для целевой функции все Гi > 0. Имеем случай 1, следовательно, последнее базисное решение является оптимальным.
Ответ : Фmin= 3/2, оптимальное решение (3/2; 0; 0; 1/2; 11/2).